An LDPC code, an example of which is shown in FIG. 1, is a linear code defined by a parity-check matrix in which the number of is is sparse (in other words, a majority of the matrix elements are 0 and the number of is in proportion to the whole is small). When, at this time, the size of the parity-check matrix is set at m×n (where m<n), as shown in FIG. 2, a code length of the LDPC code is n and a rank of the parity-check matrix corresponds to a parity bit length m. When the parity-check matrix is a full rank matrix (i.e. when the rank matches the number of rows), the parity bit length is m and an information sequence length is n-m.
A sum-product decoding method, such as that described in PTL 1, for example, may be cited as a representative decoding method for decoding an LDPC code. In the sum-product decoding method, decoding is performed by performing an iterative operation while calculating a log likelihood ratio (referred to hereafter as an LLR) as probabilistic reliability information relating to a received signal (a received sequence). The sum-product decoding method consists of two operations known as a column operation and a row operation, and the two operations correspond respectively to the columns and rows of the parity-check matrix. When parts that perform the column operation and the row operation are mounted on a circuit or the like, the parts are referred to respectively as a column operator and a row operator, but may also be referred to respectively as a bit node and a check node.
A specific operation of the sum-product decoding method will now be described. A decoding operation is performed by repeating two operations, namely a row operation and a column operation, alternately using as input received log likelihood ratios (referred to hereafter as received LLRs) calculated from the received sequence respectively in relation to the number of bits corresponding to the code length.
In the row operation, when N(r) is set as a set of column numbers at which an element on an rth row of the parity-check matrix is 1, a row LLR εr,c is calculated in relation to each column c included in N(r) using Equation (1), shown below. On the right side of Equation (1), zr,c′ is a column LLR calculated in the column operation, to be described below, and during a first iteration of the sum-product decoding method, a received LLR λc corresponding to the column c is substituted for zr,c′.
                              [                      Numeral            ⁢                                                  ⁢            1                    ]                ⁢                                                                                                ɛ                      r            ,            c                          =                              (                                          ∏                                                      c                    ′                                    ∈                                                            N                      ⁡                                              (                        r                        )                                                              ⁢                    \                    ⁢                                          {                      c                      }                                                                                  ⁢                                                          ⁢                              sgn                ⁡                                  (                                      z                                          r                      ,                                              c                        ′                                                                              )                                                      )                    ·                      (                                          ⊗                                                      c                    ′                                    ∈                                                            N                      ⁡                                              (                        r                        )                                                              ⁢                    \                    ⁢                                          {                      c                      }                                                                                  ⁢                                                                z                                      r                    ,                                          c                      ′                                                                                                            )                                              (        1        )            
Respective operation symbols appearing on the right side of Equation (1) are defined as follows.
                              [                      Numeral            ⁢                                                  ⁢            2                    ]                ⁢                                                                                                sgn          ⁡                      (            x            )                          ⁢                  {                                                    1                                                              (                                      x                    ≥                    0                                    )                                                                                                      -                  1                                                                              (                                      x                    <                    0                                    )                                                                                        (        2        )                                          [                      Numeral            ⁢                                                  ⁢            3                    ]                ⁢                                                                                                            ⊗                          i              ∈              I                                ⁢                      z            i                          =                                            z              1                        ⊗                          z              2                        ⊗                                                  ⁢            …            ⁢                                                  ⊗                          z                                              I                                                              ⁢                                          ⁢                      (                          I              =                              {                                  1                  ,                  2                  ,                  …                  ⁢                                                                          ,                                                          I                                                                      }                                      )                                              (        3        )                                          [                      Numeral            ⁢                                                  ⁢            4                    ]                ⁢                                                                                                x          ⊗          y                =                  f          ⁡                      (                                          f                ⁡                                  (                  x                  )                                            +                              f                ⁡                                  (                  y                  )                                                      )                                              (        4        )                                          [                      Numeral            ⁢                                                  ⁢            5                    ]                ⁢                                                                                                f          ⁡                      (            x            )                          =                  ln          ⁢                                                    exp                ⁡                                  (                  x                  )                                            +              1                                                      exp                ⁡                                  (                  x                  )                                            -              1                                                          (        5        )            
Next, the column operation will be described. Here, M(c) is set as a set of rows on which an element on the column c of the parity-check matrix is 1. In the column operation, the column LLR zr,c is calculated in relation to the row LLR εr,c′ determined in the row operation using Equation (6), shown below.
                              [                      Numeral            ⁢                                                  ⁢            6                    ]                ⁢                                                                                                z                      r            ,            c                          =                              λ            c                    +                                    ∑                                                r                  ′                                ∈                                                      M                    ⁡                                          (                      c                      )                                                        ⁢                  \                  ⁢                                      {                    r                    }                                                                        ⁢                                                  ⁢                          ɛ                                                r                  ′                                ,                c                                                                        (        6        )            
Further, a transmission bit bc is estimated (a decoding result of the LDPC code is calculated) using Equation (7). When, as a result of Equation (7), zc equals or exceeds 0, a cth bit bc of the received sequence is set at 1, and when zc is smaller than 0, bc is set at 0.
                              [                      Numeral            ⁢                                                  ⁢            7                    ]                ⁢                                                                                                z          c                =                              λ            c                    +                                    ∑                              r                ∈                                  M                  ⁡                                      (                    c                    )                                                                        ⁢                                                  ⁢                          ɛ                              r                ,                c                                                                        (        7        )            
After performing the row operation on the column LLR obtained from Equation (6), the operations are repeated, and when either a predetermined upper limit number of iterations is reached or the estimated bit is a codeword (i.e. can be determined by a parity check), an estimated bit sequence bc is output, whereupon decoding is terminated.
With the sum-product decoding method, indices and logarithms must be calculated during the row operation, as illustrated in Equation (1) and Equations (2) to (5), leading to an increase in the calculation amount.
In PTL 1 and PTL 2 serving as further patent literature, several decoding methods with which the calculation amount is reduced by approximating Equation (1) are described. A min-sum decoding method using Equation (8), shown below, in place of Equation (1) may be cited as a representative approximation method.
                              [                      Numeral            ⁢                                                  ⁢            8                    ]                ⁢                                                                                                ɛ                      r            ,            c                          =                              (                                          ∏                                                      c                    ′                                    ∈                                                            N                      ⁡                                              (                        r                        )                                                              ⁢                    \                    ⁢                                          {                      c                      }                                                                                  ⁢                                                          ⁢                              sgn                ⁡                                  (                                      z                                          r                      ,                                              c                        ′                                                                              )                                                      )                    ·                                    min                                                c                  ′                                ∈                                                      N                    ⁡                                          (                      r                      )                                                        ⁢                  \                  ⁢                                      {                    c                    }                                                                        ⁢                          {                                                                z                                      r                    ,                                          c                      ′                                                                                                  }                                                          (        8        )            
In the min-sum decoding method, an operation consisting of the indices and logarithms appearing in Equation (1) is approximated by calculating a minimum value of an absolute value of zr,c, as illustrated in Equation (8).
However, the approximation precision of the min-sum decoding method is rough, and therefore the decoding performance deteriorates by a large amount in comparison with the sum-product decoding method. Accordingly, decoding methods exhibiting an improved decoding performance, albeit with a slightly larger calculation amount than the min-sum decoding method, have been devised, and one of these methods is an offset BP-based decoding method in which Equation (1) is replaced by Equation (9), shown below.
                              [                      Numeral            ⁢                                                  ⁢            9                    ]                ⁢                                                                                                ɛ                      r            ,            c                          =                                            (                                                ∏                                                            c                      ′                                        ∈                                                                  N                        ⁡                                                  (                          r                          )                                                                    ⁢                      \                      ⁢                                              {                        c                        }                                                                                            ⁢                                                                  ⁢                                  sgn                  ⁡                                      (                                          z                                              r                        ,                                                  c                          ′                                                                                      )                                                              )                        ·            max                    ⁢                      {                                                                                min                                                                  c                        ′                                            ∈                                                                        N                          ⁡                                                      (                            r                            )                                                                          ⁢                        \                        ⁢                                                  {                          c                          }                                                                                                      ⁢                                      {                                                                                        z                                                  r                          ,                                                      c                            ′                                                                                                                                      }                                                  -                α                            ,              0                        }                                              (        9        )            
In the offset BP-based decoding method, a minimum value is calculated in a similar manner to the min-sum decoding method, whereupon α is subtracted from the minimum value. α is a constant determined in advance using a density evolution method or the like. In comparison with the min-sum decoding method, only the subtraction operation is added, and therefore the increase in the calculation amount is small. The decoding performance, however, is greatly improved.
A normalized min-sum decoding method (Equation (10)) and a δ-min decoding method (see NPL 1, for example) may also be cited as decoding methods exhibiting a higher decoding performance than the min-sum decoding method, similarly to the offset BP-based decoding method, and PTL 2 discloses a decoding method in which a of the offset BP-based decoding method is made variable in accordance with the minimum value.
                              [                      Numeral            ⁢                                                  ⁢            10                    ]                ⁢                                                                                                ɛ                      r            ,            c                          =                              (                                          ∏                                                      c                    ′                                    ∈                                                            N                      ⁡                                              (                        r                        )                                                              ⁢                    \                    ⁢                                          {                      c                      }                                                                                  ⁢                                                          ⁢                              sgn                ⁡                                  (                                      z                                          r                      ,                                              c                        ′                                                                              )                                                      )                    ·          β          ·                                    min                                                c                  ′                                ∈                                                      N                    ⁡                                          (                      r                      )                                                        ⁢                  \                  ⁢                                      {                    c                    }                                                                        ⁢                          {                                                                z                                      r                    ,                                          c                      ′                                                                                                  }                                                          (        10        )            
In all of the decoding methods described above, in which an approximation operation is applied to the sum-product decoding method, a type of low calculation amount processing is performed on the minimum value of the absolute value of zr,c or a value derived therefrom (referred to hereafter as a sub-minimum value), and the obtained result is set as the row LLR εr,c.
When the sum-product decoding method or a decoding method in which an approximation operation is applied to the sum-product method is mounted on a circuit, column operators for performing the column operation and row operators for performing the row operation are mounted in respective numbers corresponding to the numbers of columns and rows on the parity-check matrix. As shown in FIG. 3, the column operators and row operators are mounted in accordance with the respective columns and rows of the parity-check matrix such that for each 1 on the matrix, a wire is laid between the corresponding column and row in order to input and output data. For example, a matrix element on the fourth row and the second column of the parity-check matrix shown in FIG. 3A is 1, and therefore a wire is laid between a row operator #4 and a column operator #2, as shown in FIG. 3B. Wires are laid similarly between the column operators and the row operators of the columns and rows where the matrix elements of the parity-check matrix are 1.